<!DOCTYPE html>
<html lang="en">
  <head>
    <meta charset="UTF-8" />
    <meta http-equiv="X-UA-Compatible" content="IE=edge" />
    <meta name="viewport" content="width=device-width, initial-scale=1.0" />
    <title>Document</title>
  </head>
  <body>
    <script>
      /* 

  二叉搜索树(BST),又称二叉排序树或二叉查找树
*/

      //封装:

      function BinarySearchTree() {
        function Node(key) {
          this.key = key
          this.left = null
          this.right = null
        }

        this.root = null

        // 提供给外部使用的插入方法
        BinarySearchTree.prototype.insert = function (key) {
          // 1. 创建新结点
          let newNode = new Node(key)

          // 2.判断有没有根节点
          if (this.root) {
            this.insertNode(this.root, newNode)
          } else {
            this.root = newNode
          }
        }
        BinarySearchTree.prototype.insertNode = function (node, newNode) {
          // 1. 比较大小
          if (node.key > newNode.key) {
            // 判断左子结点是否存在
            if (node.left) {
              this.insertNode(node.left, newNode)
            } else {
              node.left = newNode
            }
          } else {
            // 判断右子节点是否存在
            if (node.right) {
              this.insertNode(node.right, newNode)
            } else {
              node.right = newNode
            }
          }
        }
      }

      const bTree = new BinarySearchTree()
      bTree.insert(11)
      bTree.insert(7)
      bTree.insert(15)
      bTree.insert(5)
      bTree.insert(3)
      bTree.insert(9)
      bTree.insert(8)
      bTree.insert(10)
      bTree.insert(13)
      bTree.insert(12)
      bTree.insert(14)
      bTree.insert(20)
      bTree.insert(18)
      bTree.insert(25)
      bTree.insert(6)

      console.log(bTree)
    </script>
  </body>
</html>
